package ahaArithmetic;

public class heap {

    static int[] tree = new int[]{0,99,5,36,7,22,17,92,12,2,19,25,28,1,46};
    static int n = tree.length-1;

    public static void main(String[] args) {
        for(int i=n/2;i>=1;i--){
            siftDown(i);
        }
        for(int x:tree){
            System.out.print(x+" ");
        }
    }

    public static void siftDown(int i){
        int t ;  //标记最小的坐标
        int flag = 0; //标记书否需要继续向下调整
        int c;       //用于交换的中间变量

        while (flag==0 && i<=n/2){
            if(tree[i]>tree[i*2]){    //判断左儿子
                t = i*2;
            }
            else {
                t = i;
            }
            if(i*2+1<n){    //判断右儿子
                if(tree[i*2+1] < tree[t]){
                    t = i*2+1;
                }
            }
            if(t != i){
                c = tree[i];
                tree[i] = tree[t];
                tree[t] = c;
                i = t;
            }
            else{
                flag = 1;
            }
        }
    }

    public static void siftUp(int i){
        int flag = 0;
        int c;
        if(i <= 1){
            return;
        }
        while (i>1 && flag==0){
            if(tree[i] < tree[i/2]){
                c = tree[i];
                tree[i] = tree[i/2];
                tree[i/2] = c;
                i = i/2;
            }
            else {
                flag = 1;
            }
        }
    }
}
